// 给你一个长度为n的整数数组nums，其中nums的所有整数都在范围[1, n]内，且每个整数出现一次或者两次，请你找出所有出现两次的整数，并以数组的形式返回
// 要求，设计并实现一个时间复杂度为O(n)且仅使用常量额外空间的算法解决此问题

// 思路：常数级空间复杂度，那就需要数组作为哈希表，因为元素都在1-n之间，且只会 出现1或2次，则可以利用元素的正负符号来判断
// 如果第二次出现的元素找到映射的数组元素符号，如果是负数则说明该数有2次
// 时间复杂度：O(n)，n是数组的长度
// 空间复杂度：O(1)

function findDuplicates(arr) {
    let res = []
    for (let i = 0; i < arr.length; i++) {
        let val = Math.abs(arr[i])
        if (arr[val - 1] < 0) {
            res.push(val)
        } else {
            arr[val - 1] = -arr[val - 1]
        }
    }
    return res
}

let nums = [4,3,2,7,8,2,3,1]
console.log(findDuplicates(nums))